package com.LeeCode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 口算难题
 */

public class Code1307 {
    public static void main(String[] args) {
        String[] words = {"SEND", "MORE"};
        String result = "MONEY";
        System.out.println(new Code1307().isSolvable(words, result));
    }

    public boolean isSolvable(String[] words, String result) {
        Set<Character> charSet = new HashSet<>();
        Set<Character> nonZeroChars = new HashSet<>();

        for (String word : words) {
            if (word.length() > 1) {
                nonZeroChars.add(word.charAt(0));
            }
            for (char c : word.toCharArray()) {
                charSet.add(c);
            }
        }

        if (result.length() > 1) {
            nonZeroChars.add(result.charAt(0));
        }
        for (char c : result.toCharArray()) {
            charSet.add(c);
        }

        if (charSet.size() > 10) {
            return false;
        }

        Character[] chars = charSet.toArray(new Character[0]);
        int[] charMap = new int[128];
        Arrays.fill(charMap, -1);
        boolean[] used = new boolean[10];

        return backtrack(0, chars, nonZeroChars, charMap, used, words, result);
    }

    private boolean backtrack(int index, Character[] chars, Set<Character> nonZeroChars,
                              int[] charMap, boolean[] used, String[] words, String result) {
        if (index == chars.length) {
            return checkEquation(words, result, charMap);
        }

        char currentChar = chars[index];

        for (int digit = 0; digit <= 9; digit++) {
            if (used[digit]) continue;
            if (nonZeroChars.contains(currentChar) && digit == 0) continue;

            charMap[currentChar] = digit;
            used[digit] = true;

            if (backtrack(index + 1, chars, nonZeroChars, charMap, used, words, result)) {
                return true;
            }

            charMap[currentChar] = -1;
            used[digit] = false;
        }

        return false;
    }

    private boolean checkEquation(String[] words, String result, int[] charMap) {
        int sum = 0;

        for (String word : words) {
            int num = 0;
            for (char c : word.toCharArray()) {
                num = num * 10 + charMap[c];
            }
            sum += num;
        }

        int resultNum = 0;
        for (char c : result.toCharArray()) {
            resultNum = resultNum * 10 + charMap[c];
        }

        return sum == resultNum;
    }
}
